home *** CD-ROM | disk | FTP | other *** search
/ Speccy ClassiX 1998 / Speccy ClassiX 98.iso / amiga_system / the_aminet / dev / gcc / ixemulsrc.lha / ixemul-41.4 / network / dynahash.c < prev    next >
C/C++ Source or Header  |  1995-05-18  |  24KB  |  1,014 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Margo Seltzer.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)dynahash.c    5.14 (Berkeley) 4/2/91";
  39. #endif /* LIBC_SCCS and not lint */
  40. #undef DEBUG
  41. #include <sys/param.h>
  42. #include <sys/stat.h>
  43. #include <fcntl.h>
  44. #include <errno.h>
  45. #include <assert.h>
  46. #include <db.h>
  47. #include <stdio.h>
  48. #include <stdlib.h>
  49. #include <unistd.h>
  50. #include <string.h>
  51. #include "hash.h"
  52.  
  53. /* Fast arithmetic, relying on powers of 2, */
  54.  
  55. #define MOD(x,y)        ((x) & ((y)-1))
  56. #define RETURN_ERROR(ERR,LOC)    { save_errno = ERR; goto LOC; }
  57.  
  58. /* Return values */
  59.  
  60. #define    SUCCESS    0
  61. #define    ERROR    -1
  62. #define    ABNORMAL 1
  63.  
  64. /* page.c */
  65. extern int __get_page();
  66. extern int __split_page();
  67. extern int __addel();
  68. extern int __delpair();
  69. extern u_long *__init_bitmap();
  70.  
  71. /* big.c */
  72. extern int __big_return();
  73. extern int __big_keydata();
  74. extern u_short __find_last_page();
  75.  
  76. /* buf.c */
  77. extern BUFHEAD    *__get_buf();
  78. extern void __buf_init();
  79. extern int __buf_free();
  80.  
  81. /* hash function */
  82. extern int (*default_hash)();
  83.  
  84. /* My externals */
  85. extern int __expand_table();
  86. extern u_int __call_hash();
  87.  
  88. /* Internal routines */
  89. static HTAB *init_hash();
  90. static int hash_access();
  91. static int flush_meta();
  92. static int alloc_segs();
  93. static int init_htab();
  94. static char *hash_realloc();
  95. static int hdestroy();
  96. static int hash_put();
  97. static int hash_delete();
  98. static int hash_get();
  99. static int hash_sync();
  100. static int hash_close();
  101. static int hash_seq();
  102. static void swap_header_copy();
  103. static void swap_header();
  104.  
  105. /* Local data */
  106.  
  107. HTAB *hashp = NULL;
  108.  
  109. #ifdef HASH_STATISTICS
  110. long hash_accesses, hash_collisions, hash_expansions, hash_overflows;
  111. #endif
  112.  
  113. /************************** INTERFACE ROUTINES **********************/
  114. /* OPEN/CLOSE */
  115.  
  116. extern    DB *
  117. hash_open ( file, flags, mode, info )
  118. const char    *file;
  119. int    flags;
  120. int    mode;
  121. const HASHINFO    *info;        /* Special directives for create */
  122. {
  123.     int        buckets;
  124.     int        bpages;
  125.     int        hdrsize;
  126.     int        i;
  127.     int        new_table = 0;
  128.     int        nkey;
  129.     int        nsegs;
  130.     int        save_errno;
  131.     struct    stat statbuf;
  132.     DB        *dbp;
  133.  
  134.  
  135.     if ( !(hashp = (HTAB *) calloc( 1, sizeof(HTAB) ))) {
  136.     /* calloc should set errno */
  137.     return(0);
  138.     }
  139.     hashp->fp = -1;
  140.     /* 
  141.     Select flags relevant to us.
  142.     Even if user wants write only, we need to be able to read 
  143.     the actual file, so we need to open it read/write.  But, the
  144.     field in the hashp structure needs to be accurate so that
  145.     we can check accesses.
  146.     */
  147.     flags = flags & (O_CREAT | O_EXCL | O_RDONLY | O_RDWR | O_TRUNC | O_WRONLY);
  148.     hashp->flags = flags;
  149.     if ( flags & O_WRONLY )  flags = (flags & ~O_WRONLY) | O_RDWR;
  150.  
  151.     if ( !file || 
  152.      (flags & O_TRUNC) || 
  153.      (stat ( file, &statbuf ) && (errno == ENOENT)) ) {
  154.      if ( errno == ENOENT ) {
  155.         errno = 0;        /* Just in case someone looks at errno */
  156.      }
  157.      new_table = 1;
  158.     }
  159.  
  160.     if ( file ) {
  161.     if ((hashp->fp = open ( file, flags, mode )) == -1) {
  162.         RETURN_ERROR (errno, error0);
  163.     }
  164.     (void)fcntl(hashp->fp, F_SETFD, 1);
  165.     }
  166.  
  167.     if ( new_table ) {
  168.     if ( !(hashp = init_hash( info )) ) {
  169.         RETURN_ERROR(errno,error1);
  170.     }
  171.     } else {
  172.     /* Table already exists */
  173.     if ( info && info->hash ) hashp->hash = info->hash;
  174.     else hashp->hash = default_hash;
  175.  
  176.     hdrsize = read ( hashp->fp, &hashp->hdr, sizeof(HASHHDR) );
  177. #if BYTE_ORDER == LITTLE_ENDIAN
  178.     swap_header ( );
  179. #endif
  180.     if ( hdrsize == -1 ) {
  181.         RETURN_ERROR(errno, error1);
  182.     }
  183.     if ( hdrsize != sizeof(HASHHDR) ) {
  184.         RETURN_ERROR(EFTYPE, error1);
  185.     }
  186.  
  187.     /* Verify file type, versions and hash function */
  188.     if ( hashp->MAGIC != HASHMAGIC ) 
  189.         RETURN_ERROR ( EFTYPE, error1 );
  190.     if ( hashp->VERSION != VERSION_NO ) 
  191.         RETURN_ERROR ( EFTYPE, error1 );
  192.     if (hashp->hash ( CHARKEY, sizeof(CHARKEY) ) != hashp->H_CHARKEY ) {
  193.         RETURN_ERROR ( EFTYPE, error1 );
  194.     }
  195.  
  196.     /* 
  197.         Figure out how many segments we need.
  198.     */
  199.     nsegs = (hashp->MAX_BUCKET + hashp->SGSIZE -1)/ hashp->SGSIZE;
  200.     hashp->nsegs = 0;
  201.     if (alloc_segs( nsegs )) {    
  202.         /* 
  203.         If alloc_segs fails, table will have been destroyed 
  204.         and errno will have been set.
  205.         */
  206.         return( (DB *) NULL );
  207.     }
  208.  
  209.     /* Read in bitmaps */
  210.     bpages = (hashp->SPARES[__log2(hashp->MAX_BUCKET)] + 
  211.           (hashp->BSIZE << BYTE_SHIFT) - 1) >> 
  212.           (hashp->BSHIFT + BYTE_SHIFT);
  213.  
  214.     hashp->nmaps = bpages;
  215.     memset ( &hashp->mapp[0], 0, bpages * sizeof ( u_long *) );
  216.     }
  217.  
  218.     /* Initialize Buffer Manager */
  219.     if ( info && info->cachesize ) {
  220.     __buf_init (info->cachesize);
  221.     } else {
  222.     __buf_init (DEF_BUFSIZE);
  223.     }
  224.  
  225.     hashp->new_file = new_table;
  226.     hashp->save_file = file && (hashp->flags & (O_WRONLY|O_RDWR));
  227.     hashp->cbucket = -1;
  228.     if ( !(dbp = (DB *)malloc ( sizeof (DB) )) ) {
  229.     save_errno = errno;
  230.     hdestroy();
  231.     errno = save_errno;
  232.     return ( NULL );
  233.     }
  234.     dbp->internal = (char *)hashp;
  235.     dbp->close = hash_close;
  236.     dbp->del = hash_delete;
  237.     dbp->get = hash_get;
  238.     dbp->put = hash_put;
  239.     dbp->seq = hash_seq;
  240.     dbp->sync = hash_sync;
  241.     dbp->type = DB_HASH;
  242.  
  243. #ifdef DEBUG
  244.     (void)fprintf(stderr, "%s\n%s%x\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%x\n%s%x\n%s%d\n%s%d\n",
  245.         "init_htab:",
  246.         "TABLE POINTER   ", hashp,
  247.         "BUCKET SIZE     ", hashp->BSIZE,
  248.         "BUCKET SHIFT    ", hashp->BSHIFT,
  249.         "DIRECTORY SIZE  ", hashp->DSIZE,
  250.         "SEGMENT SIZE    ", hashp->SGSIZE,
  251.         "SEGMENT SHIFT   ", hashp->SSHIFT,
  252.         "FILL FACTOR     ", hashp->FFACTOR,
  253.         "MAX BUCKET      ", hashp->MAX_BUCKET,
  254.         "HIGH MASK       ", hashp->HIGH_MASK,
  255.         "LOW  MASK       ", hashp->LOW_MASK,
  256.         "NSEGS           ", hashp->nsegs,
  257.         "NKEYS           ", hashp->NKEYS );
  258. #endif
  259. #ifdef HASH_STATISTICS
  260.     hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0;
  261. #endif
  262.     return (dbp);
  263.  
  264. error2:
  265.     (void)hdestroy();
  266.     errno = save_errno;
  267.     return ( (DB *)NULL );
  268.  
  269. error1:
  270.     (void) close ( hashp->fp );
  271.  
  272. error0:
  273.     free ( hashp );
  274.     errno = save_errno;
  275.     return ( (DB *) NULL );
  276. }
  277.  
  278. static int
  279. hash_close (dbp)
  280. DB    *dbp;
  281. {
  282.     int    retval;
  283.  
  284.     if ( !dbp ) {
  285.         return(ERROR);
  286.     }
  287.     hashp = (HTAB *)dbp->internal;
  288.     retval = hdestroy();
  289.     (void)free ( dbp );
  290.     return ( retval );
  291. }
  292.  
  293.  
  294. /************************** LOCAL CREATION ROUTINES **********************/
  295. static HTAB * 
  296. init_hash( info )
  297. HASHINFO *info;
  298. {
  299.     int    nelem;
  300.  
  301.     nelem = 1;
  302.  
  303.     hashp->LORDER    = BYTE_ORDER;
  304.     hashp->BSIZE    = DEF_BUCKET_SIZE;
  305.     hashp->BSHIFT   = DEF_BUCKET_SHIFT;
  306.     hashp->SGSIZE   = DEF_SEGSIZE;
  307.     hashp->SSHIFT   = DEF_SEGSIZE_SHIFT;
  308.     hashp->DSIZE    = DEF_DIRSIZE;
  309.     hashp->FFACTOR  = DEF_FFACTOR;
  310.     hashp->hash     = default_hash;
  311.     bzero (hashp->SPARES, sizeof (hashp->SPARES));
  312.  
  313.     if ( info ) {
  314.         if ( info->bsize )   {
  315.         /* Round pagesize up to power of 2 */
  316.         hashp->BSHIFT  = __log2(info->bsize);
  317.         hashp->BSIZE   = 1 << hashp->BSHIFT;
  318.         if ( hashp->BSIZE > MAX_BSIZE ) {
  319.             errno = EINVAL;
  320.             return(0);
  321.         }
  322.         }
  323.         if ( info->ffactor )  hashp->FFACTOR = info->ffactor;
  324.         if ( info->hash ) hashp->hash    = info->hash;
  325.         if ( info->nelem ) nelem = info->nelem;
  326.         if ( info->lorder ) {
  327.         if ( info->lorder != BIG_ENDIAN && 
  328.              info->lorder != LITTLE_ENDIAN) {
  329.             errno = EINVAL;
  330.             return(0);
  331.         }
  332.         hashp->LORDER = info->lorder;
  333.         }
  334.     }
  335.  
  336.     /* init_htab should destroy the table and set errno if it fails */
  337.     if ( init_htab ( nelem ) ) {
  338.         return(0);
  339.     } else {
  340.         return(hashp);
  341.     }
  342. }
  343.  
  344. /*
  345.     This calls alloc_segs which may run out of memory.
  346.     Alloc_segs will destroy the table and set errno,
  347.     so we just pass the error information along.
  348.  
  349.     Returns 0 on No Error
  350.  
  351. */
  352. static int
  353. init_htab ( nelem )
  354. int    nelem;
  355. {
  356.     register SEGMENT    *segp;
  357.     register int nbuckets;
  358.     register int nsegs;
  359.     int    l2;
  360.  
  361.  /*
  362.   * Divide number of elements by the fill factor and determine a desired
  363.   * number of buckets.  Allocate space for the next greater power of
  364.   * two number of buckets
  365.   */
  366.     nelem = (nelem - 1) / hashp->FFACTOR + 1;
  367.  
  368.     l2 = __log2(nelem);
  369.     nbuckets = 1 << l2;
  370.     nbuckets = MAX ( nbuckets, 2 );
  371.  
  372.     hashp->SPARES[l2] = l2 + 1;
  373.     hashp->SPARES[l2+1] = l2 + 1;
  374.     /* 
  375.         First bitmap page is at:
  376.         splitpoint l2
  377.         page offset 1
  378.     */
  379.     __init_bitmap ( OADDR_OF(l2,1), l2+1, 0 );
  380.  
  381.     hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1;
  382.     hashp->HIGH_MASK = (nbuckets << 1) - 1;
  383.     hashp->HDRPAGES = ((MAX(sizeof(HASHHDR),MINHDRSIZE) - 1) >> 
  384.               hashp->BSHIFT) + 1;
  385.  
  386.     nsegs = (nbuckets - 1) / hashp->SGSIZE + 1;
  387.     nsegs = 1 << __log2(nsegs);
  388.  
  389.     if ( nsegs > hashp->DSIZE ) {
  390.         hashp->DSIZE  = nsegs;
  391.     }
  392.  
  393.     return (alloc_segs ( nsegs ) );
  394. }
  395.  
  396. /********************** DESTROY/CLOSE ROUTINES ************************/
  397.  
  398. /*
  399.     Flushes any changes to the file if necessary and
  400.     destroys the hashp structure, freeing all allocated
  401.     space.
  402. */
  403. static int
  404. hdestroy()
  405. {
  406.     int    save_errno;
  407.     int    i;
  408.  
  409.     save_errno = 0;
  410.  
  411.     if (hashp != NULL) {
  412. #ifdef HASH_STATISTICS
  413.      (void)    fprintf(stderr,    "hdestroy: accesses %ld collisions %ld\n",
  414.             hash_accesses, hash_collisions);
  415.      (void)    fprintf(stderr, "hdestroy: expansions %ld\n",
  416.             hash_expansions);
  417.      (void)    fprintf(stderr, "hdestroy: overflows %ld\n",
  418.             hash_overflows);
  419.      (void)    fprintf(stderr,    "keys %ld maxp %d segmentcount %d\n",
  420.             hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs);
  421.  
  422.     for ( i = 0; i < NCACHED; i++ ) {
  423.         (void) fprintf ( stderr, "spares[%d] = %d\n", i, hashp->SPARES[i] );
  424.     }
  425. #endif
  426.  
  427.         /* 
  428.             Call on buffer manager to free buffers, and if
  429.             required, write them to disk
  430.         */
  431.         if (__buf_free(1, hashp->save_file)) {
  432.             save_errno = errno;
  433.         }
  434.         if ( hashp->dir ) {
  435.             (void)free(*hashp->dir);    /* Free initial segments */
  436.             /* Free extra segments */
  437.             while ( hashp->exsegs-- ) {
  438.             (void)free ( hashp->dir[--hashp->nsegs] );
  439.             }
  440.             (void)free(hashp->dir);
  441.         }
  442.         if (flush_meta() && !save_errno) {
  443.             save_errno = errno;
  444.         }
  445.  
  446.         /* Free Bigmaps */
  447.         for ( i = 0; i < hashp->nmaps; i++ ) {
  448.             if ( hashp->mapp[i] ) {
  449.             (void) free ( hashp->mapp[i] );
  450.             }
  451.         }
  452.  
  453.         if ( hashp->fp != -1 ) {
  454.             (void)close (hashp->fp);
  455.         }
  456.         (void)free(hashp);
  457.         hashp = NULL;
  458.     }
  459.     if ( save_errno ) {
  460.         errno = save_errno;
  461.         return(ERROR);
  462.     } else {
  463.         return(SUCCESS);
  464.     }
  465. }
  466.  
  467. /* 
  468.     Write modified pages to disk 
  469.     0 == OK
  470.     -1 ERROR
  471. */
  472. static int
  473. hash_sync(dbp)
  474. DB    *dbp;
  475. {
  476.     if ( !dbp ) {
  477.         return (ERROR);
  478.     }
  479.  
  480.     hashp = (HTAB *)dbp->internal;
  481.  
  482.     if (!hashp->save_file) return(0);
  483.     if ( __buf_free ( 0, 1 )  || flush_meta()) {
  484.         return(ERROR);
  485.     }
  486.     hashp->new_file = 0;
  487.     return(0);
  488. }
  489.  
  490. /*
  491. 0 == OK
  492. -1 indicates that errno should be set
  493. */
  494. static int
  495. flush_meta()
  496. {
  497.         int    fp;
  498.     int    hdrsize;
  499.     int    i;
  500.     int    wsize;
  501.     HASHHDR    *whdrp;
  502.     HASHHDR    whdr;
  503.  
  504.     if (!hashp->save_file) return(0);
  505.     hashp->MAGIC = HASHMAGIC;
  506.     hashp->VERSION = VERSION_NO;
  507.     hashp->H_CHARKEY = hashp->hash ( CHARKEY, sizeof(CHARKEY));
  508.  
  509.     fp = hashp->fp;
  510.     whdrp = &hashp->hdr;
  511. #if BYTE_ORDER == LITTLE_ENDIAN
  512.     whdrp = &whdr;
  513.     swap_header_copy( &hashp->hdr, whdrp );
  514. #endif
  515.     if ( (lseek (fp, 0, SEEK_SET) == -1 ) ||
  516.          ((wsize = write ( fp, whdrp, sizeof(HASHHDR))) == -1)) {
  517.         return(-1);
  518.     } else if ( wsize != sizeof(HASHHDR) ) {
  519.         errno = EFTYPE;
  520.         hashp->errno = errno;
  521.         return(-1);
  522.     }
  523.     for ( i = 0; i < NCACHED; i++ ) {
  524.         if ( hashp->mapp[i] ) {
  525.         if (!__put_page((char *)hashp->mapp[i],
  526.             hashp->BITMAPS[i], 0, 1)){
  527.             return(-1);
  528.         }
  529.         }
  530.     }
  531.     return(0);
  532. }
  533. /*******************************SEARCH ROUTINES *****************************/
  534. /*
  535.     All the access routines return 
  536.     0 on SUCCESS
  537.     1 to indicate an external ERROR (i.e. key not found, etc)
  538.     -1 to indicate an internal ERROR (i.e. out of memory, etc)
  539. */
  540. static int
  541. hash_get ( dbp, key, data, flag )
  542. DB    *dbp;
  543. DBT    *key, *data;
  544. u_int    flag;
  545. {
  546. #ifdef lint
  547.     flag = flag;
  548. #endif
  549.  
  550.     if ( !dbp ) {
  551.     return (ERROR);
  552.     }
  553.     hashp = (HTAB *)dbp->internal;
  554.     if ( hashp->flags & O_WRONLY ) {
  555.     errno = EBADF;
  556.     hashp->errno = errno;
  557.     return ( ERROR );
  558.     }
  559.     return ( hash_access ( HASH_GET, key, data ) );
  560. }
  561.  
  562. static int
  563. hash_put ( dbp, key, data, flag )
  564. DB    *dbp;
  565. DBT     *key, *data;
  566. u_int    flag;
  567. {
  568.     if ( !dbp ) {
  569.     return (ERROR);
  570.     }
  571.     hashp = (HTAB *)dbp->internal;
  572.     if ( (hashp->flags & O_ACCMODE) == O_RDONLY ) {
  573.     errno = EBADF;
  574.     hashp->errno = errno;
  575.     return ( ERROR );
  576.     }
  577.     if ( flag == R_NOOVERWRITE ) {
  578.     return ( hash_access ( HASH_PUTNEW, key, data ) );
  579.     } else {
  580.     return ( hash_access ( HASH_PUT, key, data ) );
  581.     }
  582. }
  583.  
  584. static int
  585. hash_delete ( dbp, key, flag )
  586. DB    *dbp;
  587. DBT     *key;
  588. u_int    flag;        /* Ignored */
  589. {
  590. #ifdef lint
  591.     flag = flag;
  592. #endif
  593.     if ( !dbp ) {
  594.     return (ERROR);
  595.     }
  596.     hashp = (HTAB *)dbp->internal;
  597.     if ( (hashp->flags & O_ACCMODE) == O_RDONLY ) {
  598.     errno = EBADF;
  599.     hashp->errno = errno;
  600.     return ( ERROR );
  601.     }
  602.     return ( hash_access ( HASH_DELETE, key, NULL ) );
  603. }
  604.  
  605. /*
  606.     Assume that hashp has been set in wrapper routine
  607. */
  608. static int
  609. hash_access(action, key, val)
  610. ACTION action;
  611. DBT *key, *val;
  612. {
  613.     register    BUFHEAD    *rbufp;
  614.     register    u_short    *bp;
  615.     register    int    ndx;
  616.     register     int n;
  617.     register     int off = hashp->BSIZE;
  618.     register    int        size;
  619.     register    char    *kp;
  620.     BUFHEAD    *bufp;
  621.     BUFHEAD    *save_bufp;
  622.     u_short    pageno;
  623.  
  624. #ifdef HASH_STATISTICS
  625.     hash_accesses++;
  626. #endif
  627.  
  628.     size = key->size;
  629.     kp = (char *)key->data;
  630.     rbufp = __get_buf ( __call_hash(kp, size), NULL, 0 );
  631.     if ( !rbufp ) return(ERROR);
  632.     save_bufp = rbufp;
  633.  
  634.     /* Pin the bucket chain */
  635.     rbufp->flags |= BUF_PIN;
  636.     for ( bp = (u_short *)rbufp->page, n = *bp++, ndx = 1; ndx < n;  ) {
  637.         if ( bp[1] >= REAL_KEY ) {
  638.         /* Real key/data pair */
  639.         if (size == off - *bp && 
  640.             bcmp(kp, rbufp->page + *bp, size) == 0) {
  641.             goto found;
  642.         }
  643.         off = bp[1];
  644. #ifdef HASH_STATISTICS
  645.         hash_collisions++;
  646. #endif
  647.             bp += 2; 
  648.             ndx += 2;
  649.         } else if ( bp[1] == OVFLPAGE ) {
  650.         rbufp = __get_buf ( *bp, rbufp, 0 );
  651.         if ( !rbufp ) {
  652.             save_bufp->flags &= ~BUF_PIN;
  653.             return (ERROR);
  654.         }
  655.         /* FOR LOOP INIT */
  656.         bp = (u_short *)rbufp->page;
  657.         n = *bp++;
  658.         ndx = 1;
  659.         off = hashp->BSIZE;
  660.         } else if ( bp[1] < REAL_KEY ) {
  661.         if ( (ndx = __find_bigpair(rbufp, ndx, kp, size )) > 0 ) {
  662.             goto found;
  663.         } else if ( ndx == -2 ) {
  664.             bufp = rbufp;
  665.             if ( !(pageno = __find_last_page ( &bufp )) ) {
  666.             ndx = 0;
  667.             rbufp = bufp;
  668.             break;    /* FOR */
  669.             }
  670.             rbufp = __get_buf ( pageno, bufp, 0 );
  671.             if ( !rbufp ) {
  672.             save_bufp->flags &= ~BUF_PIN;
  673.             return (ERROR);
  674.             }
  675.             /* FOR LOOP INIT */
  676.             bp = (u_short *)rbufp->page;
  677.             n = *bp++;
  678.             ndx = 1;
  679.             off = hashp->BSIZE;
  680.         } else  {
  681.             save_bufp->flags &= ~BUF_PIN;
  682.             return(ERROR);
  683.         }
  684.         } 
  685.     }
  686.  
  687.     /* Not found */
  688.     switch ( action ) {
  689.         case HASH_PUT:
  690.         case HASH_PUTNEW:
  691.         if (__addel(rbufp, key, val)) {
  692.             save_bufp->flags &= ~BUF_PIN;
  693.             return(ERROR);
  694.         } else {
  695.             save_bufp->flags &= ~BUF_PIN;
  696.             return(SUCCESS);
  697.         }
  698.         case HASH_GET:
  699.         case HASH_DELETE:
  700.         default:
  701.         save_bufp->flags &= ~BUF_PIN;
  702.         return(ABNORMAL);
  703.     }
  704.  
  705. found:
  706.     switch (action) {
  707.         case HASH_PUTNEW:
  708.         save_bufp->flags &= ~BUF_PIN;
  709.         return(ABNORMAL);
  710.         case HASH_GET:
  711.         bp = (u_short *)rbufp->page;
  712.         if (bp[ndx+1] < REAL_KEY) __big_return(rbufp, ndx, val, 0);
  713.         else {
  714.             val->data = (u_char *)rbufp->page + (int) bp[ndx + 1];
  715.             val->size = bp[ndx] - bp[ndx + 1];
  716.         }
  717.         break;
  718.         case HASH_PUT:
  719.         if ((__delpair (rbufp, ndx)) || (__addel (rbufp, key, val)) ) {
  720.             save_bufp->flags &= ~BUF_PIN;
  721.             return(ERROR);
  722.         }
  723.         break;
  724.         case HASH_DELETE:
  725.         if (__delpair (rbufp, ndx))return(ERROR);
  726.         break;
  727.     }
  728.     save_bufp->flags &= ~BUF_PIN;
  729.     return (SUCCESS);
  730. }
  731.  
  732. static int
  733. hash_seq(dbp, key, data, flag)
  734. DB    *dbp;
  735. DBT     *key, *data;
  736. u_int    flag;
  737. {
  738.     register    u_int bucket;
  739.     register    BUFHEAD    *bufp;
  740.     BUFHEAD    *save_bufp;
  741.     u_short    *bp;
  742.     u_short    ndx;
  743.     u_short    pageno;
  744.  
  745.     if ( !dbp ) {
  746.         return (ERROR);
  747.     }
  748.  
  749.     hashp = (HTAB *)dbp->internal;
  750.     if ( hashp->flags & O_WRONLY ) {
  751.         errno = EBADF;
  752.         hashp->errno = errno;
  753.         return ( ERROR );
  754.     }
  755. #ifdef HASH_STATISTICS
  756.     hash_accesses++;
  757. #endif
  758.  
  759.     if ( (hashp->cbucket < 0) || (flag == R_FIRST) ) {
  760.         hashp->cbucket = 0;
  761.         hashp->cndx = 1;
  762.         hashp->cpage = NULL;
  763.     }
  764.  
  765.     if ( !(bufp = hashp->cpage) ) {
  766.         for (bucket = hashp->cbucket; 
  767.          bucket <= hashp->MAX_BUCKET; 
  768.          bucket++, hashp->cndx = 1 ) {
  769.  
  770.         bufp = __get_buf ( bucket, NULL, 0 );
  771.         if (!bufp) return(ERROR);
  772.         hashp->cpage = bufp;
  773.         bp = (u_short *)bufp->page;
  774.         if (bp[0]) break;
  775.         }
  776.         hashp->cbucket = bucket;
  777.         if ( hashp->cbucket > hashp->MAX_BUCKET ) {
  778.         hashp->cbucket = -1;
  779.         return ( ABNORMAL );
  780.         } 
  781.     } else {
  782.         bp  = (u_short *)hashp->cpage->page;
  783.     }
  784.     
  785. #ifdef DEBUG
  786.     assert (bp);
  787.     assert (bufp);
  788. #endif
  789.     while ( bp[hashp->cndx+1] == OVFLPAGE ) {
  790.         bufp = hashp->cpage = __get_buf ( bp[hashp->cndx], bufp, 0 );
  791.         if (!bufp) return(ERROR);
  792.         bp = (u_short *)(bufp->page);
  793.         hashp->cndx = 1;
  794.     }
  795.     ndx = hashp->cndx;
  796.     if (bp[ndx+1] < REAL_KEY) {
  797.         if (__big_keydata(bufp, ndx, key, data, 1)) {
  798.         return(ERROR);
  799.         }
  800.     } else {
  801.         key->data = (u_char *)hashp->cpage->page + bp[ndx];
  802.         key->size = (ndx > 1 ? bp[ndx-1] : hashp->BSIZE) - bp[ndx];
  803.         data->data = (u_char *)hashp->cpage->page + bp[ndx + 1];
  804.         data->size = bp[ndx] - bp[ndx + 1];
  805.         ndx += 2;
  806.         if ( ndx > bp[0] ) {
  807.         hashp->cpage = NULL;
  808.         hashp->cbucket++;
  809.         hashp->cndx=1;
  810.         } else hashp->cndx = ndx;
  811.     }
  812.     return (SUCCESS);
  813. }
  814.  
  815. /********************************* UTILITIES ************************/
  816. /*
  817.     0 ==> OK
  818.     -1 ==> Error
  819. */
  820. extern int
  821. __expand_table()
  822. {
  823.     u_int    old_bucket, new_bucket;
  824.     int    new_segnum;
  825.     int    dirsize;
  826.     int    spare_ndx;
  827.     register    char **old, **new;
  828. #ifdef HASH_STATISTICS
  829.     hash_expansions++;
  830. #endif
  831.  
  832.     new_bucket = ++hashp->MAX_BUCKET;
  833.     old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK);
  834.  
  835.     new_segnum = new_bucket >> hashp->SSHIFT;
  836.  
  837.     /* Check if we need a new segment */
  838.     if ( new_segnum >= hashp->nsegs ) {
  839.  
  840.         /* Check if we need to expand directory */
  841.         if ( new_segnum >= hashp->DSIZE ) {
  842.  
  843.         /* Reallocate directory */
  844.         dirsize = hashp->DSIZE * sizeof ( SEGMENT * );
  845.         if (!hash_realloc ( &hashp->dir, dirsize, (dirsize << 1 ) )) {
  846.             return(-1);
  847.         }
  848.         hashp->DSIZE = dirsize << 1;
  849.         }
  850.         if (!(hashp->dir[new_segnum] = 
  851.             (SEGMENT)calloc ( hashp->SGSIZE, sizeof(SEGMENT)))) {
  852.             return(-1);
  853.         }
  854.         hashp->exsegs++;
  855.         hashp->nsegs++;
  856.     }
  857.  
  858.     /*
  859.         If the split point is increasing (MAX_BUCKET's log
  860.         base 2 increases), we need to copy the current contents
  861.         of the spare split bucket to the next bucket
  862.     */
  863.     spare_ndx = __log2(hashp->MAX_BUCKET);
  864.     if ( spare_ndx != (__log2(hashp->MAX_BUCKET - 1))) {
  865.         hashp->SPARES[spare_ndx] = hashp->SPARES[spare_ndx-1];
  866.     }
  867.  
  868.     if ( new_bucket > hashp->HIGH_MASK ) {
  869.         /* Starting a new doubling */
  870.         hashp->LOW_MASK = hashp->HIGH_MASK;
  871.         hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK;
  872.     }
  873.  
  874.     /*
  875.      * Relocate records to the new bucket
  876.      */
  877.     return(__split_page ( old_bucket, new_bucket ));
  878. }
  879. /*
  880.     If realloc guarantees that the pointer is not destroyed
  881.     if the realloc fails, then this routine can go away
  882. */
  883. static char * 
  884. hash_realloc ( p_ptr, oldsize, newsize )
  885. char    **p_ptr;
  886. int    oldsize;
  887. int    newsize;
  888. {
  889.     register char    *p;
  890.  
  891.     if (p = (char *)malloc ( newsize ) ) {
  892.         bcopy ( *p_ptr, p, oldsize );
  893.         bzero ( *p_ptr + oldsize, newsize-oldsize );
  894.         free(*p_ptr);
  895.         *p_ptr = p;
  896.     }
  897.     return (p);
  898. }
  899.  
  900. extern u_int
  901. __call_hash ( k, len )
  902. char    *k;
  903. int    len;
  904. {
  905.     int    n, bucket;
  906.     n = hashp->hash(k, len);
  907.  
  908.     bucket = n & hashp->HIGH_MASK;
  909.     if ( bucket > hashp->MAX_BUCKET ) {
  910.         bucket = bucket & hashp->LOW_MASK;
  911.     }
  912.  
  913.     return(bucket);
  914. }
  915.  
  916. /*
  917.     Allocate segment table.  On error, destroy the table
  918.     and set errno.
  919.  
  920.     Returns 0 on success
  921. */
  922. static int
  923. alloc_segs ( nsegs )
  924. int    nsegs;
  925. {
  926.     register int    i;
  927.     register SEGMENT    store;
  928.  
  929.     int    save_errno;
  930.  
  931.     if (!(hashp->dir = (SEGMENT *)calloc(hashp->DSIZE, sizeof(SEGMENT *)))) {
  932.     save_errno = errno;
  933.     (void)hdestroy();
  934.     errno = save_errno;
  935.     return(-1);
  936.     }
  937.  
  938.     /* Allocate segments */
  939.     store = (SEGMENT)calloc ( nsegs << hashp->SSHIFT, sizeof (SEGMENT) );
  940.     if ( !store ) {
  941.     save_errno = errno;
  942.     (void)hdestroy();
  943.     errno = save_errno;
  944.     return(-1);
  945.     }
  946.  
  947.     for ( i=0; i < nsegs; i++, hashp->nsegs++ ) {
  948.     hashp->dir[i] = &store[i<<hashp->SSHIFT];
  949.     }
  950.     return(0);
  951. }
  952.  
  953. /*
  954.     Hashp->hdr needs to be byteswapped.
  955. */
  956. static void
  957. swap_header_copy ( srcp, destp )
  958. HASHHDR    *srcp;
  959. HASHHDR    *destp;
  960. {
  961.     int i;
  962.  
  963.     BLSWAP_COPY(srcp->magic, destp->magic);
  964.     BLSWAP_COPY(srcp->version, destp->version);
  965.     BLSWAP_COPY(srcp->lorder, destp->lorder);
  966.     BLSWAP_COPY(srcp->bsize, destp->bsize);
  967.     BLSWAP_COPY(srcp->bshift, destp->bshift);
  968.     BLSWAP_COPY(srcp->dsize, destp->dsize);
  969.     BLSWAP_COPY(srcp->ssize, destp->ssize);
  970.     BLSWAP_COPY(srcp->sshift, destp->sshift);
  971.     BLSWAP_COPY(srcp->max_bucket, destp->max_bucket);
  972.     BLSWAP_COPY(srcp->high_mask, destp->high_mask);
  973.     BLSWAP_COPY(srcp->low_mask, destp->low_mask);
  974.     BLSWAP_COPY(srcp->ffactor, destp->ffactor);
  975.     BLSWAP_COPY(srcp->nkeys, destp->nkeys);
  976.     BLSWAP_COPY(srcp->hdrpages, destp->hdrpages);
  977.     BLSWAP_COPY(srcp->h_charkey, destp->h_charkey);
  978.     for ( i=0; i < NCACHED; i++ ) {
  979.     BLSWAP_COPY ( srcp->spares[i] , destp->spares[i]);
  980.     BSSWAP_COPY ( srcp->bitmaps[i] , destp->bitmaps[i]);
  981.     }
  982.     return;
  983. }
  984.  
  985. static void
  986. swap_header ( )
  987. {
  988.     HASHHDR    *hdrp;
  989.     int    i;
  990.  
  991.     hdrp = &hashp->hdr;
  992.  
  993.     BLSWAP(hdrp->magic);
  994.     BLSWAP(hdrp->version);
  995.     BLSWAP(hdrp->lorder);
  996.     BLSWAP(hdrp->bsize);
  997.     BLSWAP(hdrp->bshift);
  998.     BLSWAP(hdrp->dsize);
  999.     BLSWAP(hdrp->ssize);
  1000.     BLSWAP(hdrp->sshift);
  1001.     BLSWAP(hdrp->max_bucket);
  1002.     BLSWAP(hdrp->high_mask);
  1003.     BLSWAP(hdrp->low_mask);
  1004.     BLSWAP(hdrp->ffactor);
  1005.     BLSWAP(hdrp->nkeys);
  1006.     BLSWAP(hdrp->hdrpages);
  1007.     BLSWAP(hdrp->h_charkey);
  1008.     for ( i=0; i < NCACHED; i++ ) {
  1009.     BLSWAP ( hdrp->spares[i] );
  1010.     BSSWAP ( hdrp->bitmaps[i] );
  1011.     }
  1012.     return;
  1013. }
  1014.